class PSPACE

Definition

$\mathbf{PSPACE}$ represents decision problems decidable in polynomial amounts of space, i.e.

(SPACE)

Proposition

P $\subseteq$ NP $\subseteq$ PH $\subseteq \mathbf{PSPACE} =$ NPSPACE $\subseteq$ EXPTIME

Notes

• PSPACE and NSPACE can be thought of as the space analogs of time complexity classes P and NP respectively

See also

• NPSPACE
• L
• NL
• P versus NP problem
• SPACE

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 81.
2. https://home.csulb.edu/~tebert/teaching/lectures/419-519/pspace/pspace.pdf
3. https://webdocs.cs.ualberta.ca/~zacharyf/courses/complexity_2019/notes/complexity-w19-lec03.pdf
4. https://mathoverflow.net/questions/39690/how-is-p-related-to-other-complexity-classes